package LinkedList;

/**
 * @Author: 吕庆龙
 * @Date: 2019/9/28 12:17
 * <p>
 * 功能描述:
 */
public class DoubleLinkedListAndJoseph {
    public static void main(String[] args) {
        DoubleLinkedList list = new DoubleLinkedList();
//        People people1 = new People(1);
//        People people2 = new People(2);
//        People people3 = new People(3);
//        People people4 = new People(4);
//        People people5 = new People(5);
//
//        list.add(people2);
//        list.add(people1);
//        list.add(people5);
//        list.add(people4);
//        list.add(people3);
        list.addByNum(25);
        list.cout(1,2,25);



    }
}

class DoubleLinkedList{
    People first = null;


    /**
     * 功能描述: 一个一个的添加
     */
    public void add(People people){
        //如果添加的是第一个节点
        if (first == null){
            first = people;
            first.next = first;
            return;
        }

        People temp = first;
        while(true){
            if(temp.next == first){
                temp.next = people;
                people.next = first;
                break;
            }
            temp = temp.next;//先找到最后一个节点
        }
    }

    public void list(){
        People current = first;

        while(true){
            System.out.println(current);
            if(current.next == first){
                break;
            }
            current = current.next;
        }
    }

    /**
     * 功能描述: 通过数字来添加链表,为约瑟夫问题做准备
     */
    public void addByNum(Integer num){
        if(num < 1){
            System.out.println("参数不合法!");
        }
        People current = null;
        //开始构造对象
        for (int i = 1; i <= num ; i++) {
            People people = new People(i);
            if(i == 1){
                first = people;
                first.next = first;
                current = first;
                continue;
            }
            current.next = people;
            people.next = first;
            current = people;
        }
    }

    /**
     * 约瑟夫问题
     * 问题描述: 设编号为1,2,3...,n的n个人围坐一圈。约定编号为k的人从1开始报数,数到m的人出列。它的下一位
     * 又从1开始报数,数到m的人又出列,依此类推,知道所有人都出列位置,求出列的序号顺序
     *
     * 参数描述: k->从第几个序号开始报数,m->数到几出列,n->刚开始圈里总共有几个人
     *
     */
    public void cout(Integer k,Integer m,Integer n){

        //定义一个辅助指针helper,使其总是指向first的后面一个节点
        People helper = first;
        while(true){
            if(helper.next == first){
                break;
            }
            helper = helper.next;
        }

        //先让first指针指向序列号为k的人
        for (int i = 0; i < k - 1; i++) {
            helper = helper.next;
            first = first.next;
        }

        //开始报号
        while(true){
            if(helper == first){
                break;
            }

            for (int i = 0; i < m - 1; i++) {
                helper = helper.next;
                first = first.next;
            }
            System.out.println(first.No);
            helper.next = first.next;
            first = helper.next;
        }
        System.out.println("最后一个出圈:" + first.No);

    }
}

class People{
    Integer No;
    People next;

    public People(Integer no) {
        No = no;
    }

    @Override
    public String toString() {
        return "People{" +
                "No=" + No +
                '}';
    }
}